package lc20240619;

public class SearchTwoDimensionMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        
        // Initialize the start and end pointers for binary search
        int start = 0;
        int end = rows * cols - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            //获取行数和列数
            int midValue=matrix[mid/cols][mid%cols];

            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        SearchTwoDimensionMatrix solution = new SearchTwoDimensionMatrix();
        int[][] matrix = {
            {1, 3, 5, 7},
            {10, 11, 16, 20},
            {23, 30, 34, 60}
        };
        int target = 3;
        boolean result = solution.searchMatrix(matrix, target);
        System.out.println("The target " + target + " is in the matrix: " + result);
    }
}
